package algorithme;

import model.Arc;
import model.Graph;
import model.Noeud;

import java.util.HashMap;

/** Created with IntelliJ IDEA.
 * User: Thomas
 * Date: 04/02/14 * Time: 10:57
 * To change this template use File | Settings | File Templates.
 */
public class AlgorithmeExplorationArborescente extends AlgorithmePlusCourtChemin {

    private HashMap<Integer, LinkedListNoeudPath> distances;

    /**
     * Recherche le plus court chemin par l'algorithme d'exploration arborescente
     * @param graph le graph dans lequel se situe la recherche
     * @param source le noeud de départ
     * @param destination le noeud de destination
     * @return la liste chainée de destination vers la source
     */
    @Override
    protected LinkedListNoeudPath plusCourtChemin(Graph graph, Noeud source, Noeud destination) {
        //Initialisation du tableau des distances
        distances = this.initTableauDistance(graph,source);

        //début de la recursion
        parcours_prof(source);

        //parcours du chemin trouvé à l'envers, destination -> source
        return distances.get(destination.getId());
    }

    private void parcours_prof(Noeud noeud){

        //Parcours de tous les noeuds partant du noeud courant
        for (Arc arc : noeud.getNext()) {

            //LinkedListNoeudPath de destination de l'arc courant
            LinkedListNoeudPath destinationLinked = distances.get(arc.getDestination().getId());
            //LinkedListNoeudPath de source de l'arc courant
            LinkedListNoeudPath sourceLinked = distances.get(arc.getSource().getId());

            double d = sourceLinked.getDistance() + arc.getCout();

            //si la distance est plus courte ou si la distance est égal et qu'il y a moins de correspondance
            if ( d < destinationLinked.getDistance() ||
                    (d == destinationLinked.getDistance() && destinationLinked.getNbCorrespondance() > sourceLinked.getNbCorrespondance()) ) {

                //on modifie ou on ajoute un prédécesseur
                destinationLinked.setDistance(d);
                destinationLinked.setPrevious(sourceLinked);
                destinationLinked.setArc(arc);

                //si l'arc courant est une correspondance on incrémente
                if (arc.getLigne().equals("0")) {
                    destinationLinked.setNbCorrespondance(sourceLinked.getNbCorrespondance() + 1);
                } else {
                    destinationLinked.setNbCorrespondance(sourceLinked.getNbCorrespondance());
                }

                //récursion
                parcours_prof(arc.getDestination());
            }
        }
    }
}